public class MatrixChainTest
{
    public  static void  main(String [] args)
    {
        int p[]={30,35,15,5,10,20,25};
        MatrixChain mc=new MatrixChain(p);
        mc.solve();

        
    }
}
 class MatrixChain
{
    private int m[][];
    private int s[][];
    public int p[];
    public MatrixChain(int [] p0)
    {
        p=p0;
    }
    public void solve()
    {
        m=new int[p.length][p.length];
        s=new int[p.length-1][p.length];
        MatrixChainOrder();
        System.out.printf("最少乘次数:%d\n",m[1][p.length-1]);
        PrintOptimalParens(1, p.length-1);
        System.out.println();
       
    }
    private void MatrixChainOrder()
    {
        int n=p.length-1;
        for(int i=1;i<=n;i++)
        {
            m[i][i]=0;
        }
        for(int l=2;l<=n;l++)
        {
            for(int i=1;i<=n-l+1;i++)
            {
                int j=i+l-1;
                m[i][j]=Integer.MAX_VALUE;
                for(int k=i;k<=j-1;k++)
                {
                    int q=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                    if(q<m[i][j])
                    {
                        m[i][j]=q;
                        s[i][j]=k;
                    }
                }
            }
        }

    }
    private void PrintOptimalParens(int i,int j)
    {
        if(i==j)
        {
            System.out.print("A"+i);
        }
        else
        {
            System.out.print("(");
            PrintOptimalParens(i,s[i][j]);
            PrintOptimalParens(s[i][j]+1,j);
            System.out.print(")");
        }
    }

}